This invention relates generally to encoding/decoding method and apparatus and recording medium, and more particularly, to an encoding method and apparatus, a decoding method and apparatus, and a recording medium usable in a system for high efficiency picture encoding or decoding for efficient picture transmission.
The International organization for Standardization (ISO) has promulgated a standard for a conventional picture compression system called Joint Photographic Expert Group (JPEG). This system provides optimal encoding or decoding of pictures by applying a Discrete Cosine Transformation (DCT) to an image to transform that image into DCT coefficients. This system works most efficiently when a relatively large number of bits are to be employed to represent the encoded information. However, if the number of bits to be employed to represent the encoded information is less than a certain predetermined value, block distortion inherent in such a DCT transform becomes prevalent enough to deteriorate the quality of the picture which may be noticed by a viewer.
In response to these deficiencies of the JPEG and DCT procedure, a new Iterated Function System (IFS) picture compression technique has been proposed, and is beginning to gain favor. This IFS technique exploits self-similarity between portions of pictures and is based on fractal geometry. IFS works on the assumption that various portions of a particular picture are analogous, even though they may be of a different size, position, perspective, or orientation. IFS utilizes this redundancy in pictures to efficiently encode the picture without resulting block distortion, as may be generated in the JPEG system. Therefore, IFS is not nearly as dependent upon the number of bits to be used to represent the encoded information, and therefore the resolution during decoding does not suffer when a relatively smaller number of bits are to be used to represent the encoded information.
The basic structure of IFS is set forth in Arnaud E. Jaquin""s publication entitled xe2x80x9cImage Coding Based on a Fractal Theory of Iterated Contractive Image Transformationsxe2x80x9d, IEEE Transactions on Image Processing (Vol. 1, No. 1, pp. 18-30), and is further set forth in U.S. Pat. Nos. 5,347,600; 5,065,447 and 4,941,193, all issued to Barnsley et al. The encoding and decoding devices as generally known in the art will now be described with reference to FIGS. 15 and 16.
Referring first to FIG. 15, the conventional operation of encoding device is shown. As set forth in FIG. 15, original picture data 300 is entered to a block generating circuit 200 and is therein split into a plurality of block data 301. The entire block data 301 cover the entire original picture data 300, but the blocks do not overlap with each other. Original picture data 300 is also forwarded to reduced picture generating circuit 202. Picture data 307 having a reduced (shrunk) size, such as by way of a reduction scheme as is known in the art which is obtained through the processing of reduced picture generating circuit 202, is forwarded and stored within reduced picture storage circuit 204.
Data in each of the blocks is forwarded to approximate area search circuit 201 which searches reduced size picture data 307 stored in reduced picture storage circuit 204 to determine whether any portions of the reduced size picture data are analogous to the particular block data 301 being searched. As noted above, this search includes searching for portions of reduced size picture data 307 which are of different size, position, perspective, or orientation than the block data 301 being searched. In accordance with the detected result indicating a successful search for a most similar portion, similar block position information 306, which specifies the position of the selected portion 305 within the reduced size picture data 307 that is to be extracted, is transmitted to reduced picture storage circuit 204. Thus, in accordance with these instructions, selected portion 305 of the reduced size picture data 307 stored within reduced picture storage circuit 204 is extracted, and is transmitted to a rotation/inversion/level value transform circuit 203.
Within rotation/inversion/level value transform circuit 203, portion 305 of reduced size picture data 307 is processed by rotation/inversion/level value transformation in accordance with transformation parameters 304 which are supplied from approximate area search circuit 201. The transformation parameters 304 are indicative of the transformation which must be performed in order to transform portion 305 of reduced size picture data 307 into block data 301. These parameters are determined when a particular portion 305 of reduced size picture data 307 is found to most closely correspond to block data 301 being searched. Upon transformation at rotation/inversion/level value transform circuit 203, transformed reduced-size picture data 303 is forwarded to approximate area search circuit 201. There as a result, transformation parameters 304 and similar block position information 306 are output as ISF codes 302. Thus, a first picture is input to the system, and the output includes at least transformation parameters, for transforming a first block into a second similar block, and position information, for determining the position of the second block within the encoded picture.
Referring next to FIG. 16, decoding apparatus is provided in which the IFS codes, including transformation parameters and similar block position information 302 which are output by the encoding device of FIG. 15, are entered into and stored in an IFS code storage circuit 205. IFS codes 302 are then sequentially read out from IFS code storage circuit 205 for each block, and are forwarded to IFS code reading circuit 206. IFS code reading circuit 206 divides the codes into similar block position information 306 and transformation parameters 304 as provided by the encoder. Similar block position information 306 is then forwarded to reduced picture storage circuit 204 in order to reproduce the area of the reduced-size picture specified by similar block position information 306. The portion 305 of the reduced size picture data stored in reduced picture storage circuit 204 corresponding to the specified area is then transmitted to rotation/inversion/level value transform circuit 203, and is transformed in accordance with transformation parameters 304 which are supplied form IFS code reading circuit 206. The resulting transformed picture data 303 forwarded from rotation/inversion/level value transform circuit 203 is stored within decoded picture storage circuit 208. This procedure is performed for each block in the picture for which IFS codes are provided.
After all of the IFS codes for all of the blocks have been read out, IFS code reading circuit 206 sends a READ OUT END notification signal 310 to duplication control circuit 207. Duplication control circuit 207 counts the number of recursive decoding/duplicating operations that have been executed, and if this count has not yet reached a predetermined value, duplication control circuit 207 sends a reprocessing command signal 309 to IFS code reading circuit 206 in order to continue execution of decoding processing for all of the blocks in the picture according to a recursive decoding procedure. Simultaneously, the reprocessing command information is sent via control signal 311 to a switch 209 in order to send partially decoded picture data 313 to reduced picture generating circuit 202 via information path 314. Reduced picture generating circuit 202 then generates partially decoded reduced size picture data 315 of decoded picture data 313 in a manner similar to that as in the encoding device in order to re-write the contents of the picture stored in reduced picture storage circuit 204 and to enable a next recursive decoding step to start with partially decoded reduced picture data 315. If the proper number of recursive decoding operations have taken place, and thus the duplicating operation has been carried out the predetermined number of times, reprocessing command information is sent by a decoded picture output control signal 311 to a switch 209. Switch 209 is controlled in order to couple decoded picture data 313 output from decoded picture storage circuit 208 to a picture output port 316. Decoded picture data 313 comprises picture data of all of the decoded blocks noted above after being recursively decoded for a predetermined number of iterations and is read out from decoded picture storage circuit 208 in accordance with control signal 312.
In the above-described conventional technique, the approximate degree of similarity between blocks located at arbitrary positions in the entire picture and the reduced/transformed picture is measured, and position information of the most similar block (an approximate block position information) and a transform parameter at that time are selected from all of the possible candidates. In many cases, a reference block required in coding a certain block is located at a distant position in the picture from that certain block. In such case, a picture memory of large capacity for storing substantially all of the blocks in the picture must be retained by a decoder and encoder, and the memory must be frequently accessed. Therefore, it would be beneficial to provide an improvement which overcomes the drawbacks as set out above.
In view of the foregoing problems, it is an object of the present invention to provide an encoding device and method, a decoding device and method, an encoding and decoding device and method, an information signal transmission device, and a recording medium which enable picture restoration using a picture memory with small capacity.
In the method for iterated function coding each block in a picture, an input picture is stored in a first picture memory. Capacity information is received indicating a maximum allowable memory capacity of a second picture memory for performing an iterated function decoding of the coded picture. A search range is determined in the stored input picture; and each block is iterated function coded in accordance with the received capacity information within the determined search range.
According to one aspect of the present invention, a portion of the input picture within the determined search range is stored in a local memory.
According to another aspect of the present invention, the iterated function coding comprises generating a first picture block from the input picture, generating a plurality of second picture blocks from a portion of the input picture within the determined search range, transforming the second picture blocks according to a predetermined operation, determining a transformed second picture block that is the most similar to the first picture block, selecting a second picture block corresponding to the determined transformed second picture block, and outputting code position information indicating a position of the selected second picture block and outputting a transformation parameter representing the transformation of the selected second picture block.
In the method for producing a decoded picture from a code representing blocks of an iterated function coded picture, capacity information is generated. The generated capacity information, indicating a maximum allowable memory capacity of a picture memory for decoding the code, is outputted. According to the inventive method, the code and a transformation parameter are received: the code includes block position information for indicating a position of a picture block in a picture, and the transformation parameter represents a predetermined transform operation that has been carried out on the picture block. The picture block identified by the block position information is recursively transformed according to the received transformation parameter using the picture memory until a preselected condition is satisfied.